package leetcode.treeCode.week4.leetcode_236;

/**
 * 采用后续遍历的方式进行查找
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = dfs(root, p, q);
        return node;
    }
    private  TreeNode dfs (TreeNode node , TreeNode p , TreeNode q){
        if (node == null ) return null;
        TreeNode left = dfs(node.left, p, q);
        TreeNode right = dfs(node.right, p, q);
        if (left!=null && right != null){
            return node;
        }
        if (node == p || node == q){
            return node;
        }
        return left == null ? right : left;
    }

}